/*****************************************************************************************************************************
  This project was supported by the National Basic Research 973 Program of China under Grant No.2011CB302301
  Huazhong University of Science and Technology (HUST)   Wuhan National Laboratory for Optoelectronics

FileName: ssd.c
Author: Hu Yang		Version: 2.1	Date:2011/12/02
Description: 

History:
<contributor>     <time>        <version>       <desc>                   <e-mail>
Yang Hu	        2009/09/25	      1.0		    Creat SSDsim       yanghu@foxmail.com
2010/05/01        2.x           Change 
Zhiming Zhu     2011/07/01        2.0           Change               812839842@qq.com
Shuangwu Zhang  2011/11/01        2.1           Change               820876427@qq.com
Chao Ren        2011/07/01        2.0           Change               529517386@qq.com
Hao Luo         2011/01/01        2.0           Change               luohao135680@gmail.com
 *****************************************************************************************************************************/



#include "ssd.h"

/********************************************************************************************************************************
  1，main函数中initiatio()函数用来初始化ssd,；
  2，make_aged()函数使SSD成为aged，aged的ssd相当于使用过一段时间的ssd，里面有失效页，non_aged的ssd是新的ssd，无失效页，失效页的比例可以在初始化参数中设置；
  3，pre_process_page()函数提前扫一遍读请求，把读请求的lpn<--->ppn映射关系事先建立好，写请求的lpn<--->ppn映射关系在写的时候再建立，预处理trace防止读请求是读不到数据；
  4，simulate()是核心处理函数，trace文件从读进来到处理完成都由这个函数来完成；
  5，statistic_output()函数将ssd结构中的信息输出到输出文件，输出的是统计数据和平均数据，输出文件较小，trace_output文件则很大很详细；6，free_all_node()函数释放整个main函数中申请的节点
 *********************************************************************************************************************************/
int  main()
{
    unsigned  int i,j,k;
    struct ssd_info *ssd; //声明定义一个ssd结构

#ifdef DEBUG
    printf("enter main\n"); 
#endif

    ssd=(struct ssd_info*)malloc(sizeof(struct ssd_info)); //为ssd分配内存
    alloc_assert(ssd,"ssd");
    memset(ssd,0, sizeof(struct ssd_info)); //将ssd指向的那部分结构体内存空间清零，相当于初始化

    ssd=initiation(ssd); //初始化ssd（重点函数模块，需要仔细阅读）
    make_aged(ssd); //模拟ssd的使用情况
    pre_process_page(ssd); //读请求的预处理函数 

    for (i=0;i<ssd->parameter->channel_number;i++)
    {
        for (j=0;j<ssd->parameter->die_chip;j++)
        {
            for (k=0;k<ssd->parameter->plane_die;k++)
            {
                printf("%d,0,%d,%d:  %5d\n",i,j,k,ssd->channel_head[i].chip_head[0].die_head[j].plane_head[k].free_page);
                //将ssd的通道channel，通道上的每个芯片chip，每个芯片上的颗粒die，每个颗粒上面的闪存片plane（也就是块block），
                //每个闪存片上的闪存页page都用了结构体来进行描述，然后都实现了一个结构体数组来对每个层次的结构体进行一个关系连接；
                //所以此处的循环体相当于将ssd中按照层次分级将所有空闲状态的page按照层次的划分输出；显示当前ssd中空闲页的位置；
            }
        }
    }
    fprintf(ssd->outputfile,"\t\t\t\t\t\t\t\t\tOUTPUT\n");
    fprintf(ssd->outputfile,"****************** TRACE INFO ******************\n");

    ssd=simulate(ssd); //核心处理函数，对ssd进行一个模拟能耗过程
    statistic_output(ssd);   //输出模拟后的总结果
    /*	free_all_node(ssd);*/ //释放malloc的ssd空间

    printf("\n");
    printf("the simulation is completed!\n");

    return 1;
    /* 	_CrtDumpMemoryLeaks(); */
}


/******************simulate() *********************************************************************
 *simulate()是核心处理函数，主要实现的功能包括
 *1,从trace文件中获取一条请求，挂到ssd->request
 *2，根据ssd是否有dram分别处理读出来的请求，把这些请求处理成为读写子请求，挂到ssd->channel或者ssd上
 *3，按照事件的先后来处理这些读写子请求。
 *4，输出每条请求的子请求都处理完后的相关信息到outputfile文件中
 **************************************************************************************************/
struct ssd_info *simulate(struct ssd_info *ssd)
{
    int flag=1,flag1=0;
    double output_step=0;
    unsigned int a=0,b=0;
    //errno_t err;

    printf("\n");
    printf("begin simulating.......................\n");
    printf("\n");
    printf("\n");
    printf("   ^o^    OK, please wait a moment, and enjoy music and coffee   ^o^    \n");

    ssd->tracefile = fopen(ssd->tracefilename,"r");
    if(ssd->tracefile == NULL)
    {  
        printf("the trace file can't open\n");
        return NULL;
    }

    fprintf(ssd->outputfile,"taskid        arrive           lsn     size ope     begin time    response time    process time\n");	
    fflush(ssd->outputfile);

    while(flag!=100)      
    {

        flag=get_requests(ssd); //将请求存入请求队列中（整个ssd就一个请求队列）

        if(flag == 1) //获取指令成功。若没成功那么也不用处理新请求了
        {   
            //printf("once\n");
            if (ssd->parameter->dram_capacity!=0) //判断是否有dram
            {
                buffer_management(ssd);  
                distribute(ssd); 
            } 
            else
            {
                no_buffer_distribute(ssd);
            }		
        }
        //dispatch_CPCU(ssd->scheduler); //将调度器中的请求推入到相应单元的执行队列(论文实验新增的分发函数，可注释掉)
        process(ssd);   
        trace_output(ssd);
        if(flag == 0 && ssd->request_queue == NULL) //获取指令失败且队列空了
            flag = 100;
    }

    fclose(ssd->tracefile);
    return ssd;
}



/********    get_request    ******************************************************
 *	1.get requests that arrived already
 *	2.add those request node to ssd->reuqest_queue
 *	return	0: reach the end of the trace
 *			-1: no request has been added
 *			1: add one request to list
 *SSD模拟器有三种驱动方式:时钟驱动(精确，太慢) 事件驱动(本程序采用) trace驱动()，
 *两种方式推进事件：channel/chip状态改变、trace文件请求达到。
 *channel/chip状态改变和trace文件请求到达是散布在时间轴上的点，每次从当前状态到达
 *下一个状态都要到达最近的一个状态，每到达一个点执行一次process
 ********************************************************************************/
int get_requests(struct ssd_info *ssd)  
{  
    //不加的话可能会卡死*******************************gary add(from https://github.com/jiangyu718/ssdsim)
    if(feof(ssd->tracefile)){
        return 100; 
    }
    //*******************************gary add end

    char buffer[200]; //用到的缓冲区
    unsigned int lsn=0; 
    int device,  size, ope,large_lsn, i = 0,j=0;
    struct request *request1; //IO请求项
    int flag = 1;
    long filepoint;  //文件指针偏移量
    int64_t time_t = 0; //请求中的时间
    int64_t nearest_event_time; //寻找所有子请求的最早到达的下个状态时间

#ifdef DEBUG
    printf("enter get_requests,  current time:%lld\n",ssd->current_time);
#endif

    if(feof(ssd->tracefile))
        return 0; 

    filepoint = ftell(ssd->tracefile);	//记录文件偏移量
    fgets(buffer, 200, ssd->tracefile); 
    sscanf(buffer,"%lld %d %d %d %d",&time_t,&device,&lsn,&size,&ope);

    if ((device<0)&&(lsn<0)&&(size<0)&&(ope<0)) //判断IO参数的合理性
    {
        return 100;
    }

    //lsn小于当前ssd最小的lsn则调整当前ssd最小的lsn为IOtrace的lsn；若lsn大于当前ssd最大的lsn则调整当前ssd最大的lsn为IOtrace的lsn
    if (lsn<ssd->min_lsn) 
        ssd->min_lsn=lsn;
    if (lsn>ssd->max_lsn)
        ssd->max_lsn=lsn;

    /******************************************************************************************************
     *上层文件系统发送给SSD的任何读写命令包括两个部分（LSN，size） LSN是逻辑扇区号，对于文件系统而言，它所看到的存
     *储空间是一个线性的连续空间。例如，读请求（260，6）表示的是需要读取从扇区号为260的逻辑扇区开始，总共6个扇区。
     *large_lsn: channel下面有多少个subpage，即多少个sector。overprovide系数：SSD中并不是所有的空间都可以给用户使用，
     *比如32G的SSD可能有10%的空间保留下来留作他用，所以乘以1-provide
     ***********************************************************************************************************/
    //一个channel下面有多少个page,计算当前channel中实际上最大的逻辑扇区号large_lsn
    //large_lsn = （颗粒chip数量 × 每个颗粒chip下晶圆die的数量 × 每个晶圆die下分组plane的数量 × 每个分组plane下块block的数量 × 每个块block下页page的数量 × 每个页page下子页subpage的数量）×预留空间比例
    large_lsn=(int)((ssd->parameter->subpage_page*ssd->parameter->page_block*ssd->parameter->block_plane*ssd->parameter->plane_die*ssd->parameter->die_chip*ssd->parameter->chip_num)*(1-ssd->parameter->overprovide));
    lsn = lsn%large_lsn; //得到某个具体channel下的逻辑扇区号lsn

    nearest_event_time=find_nearest_event(ssd); //查找当前所有子请求中最早到达的下一个状态时间
    if (nearest_event_time==MAX_INT64) //判断是否等于0x7fffffffffffffff(这个参考值是代表了转换到下一状态的时间极限值)
    {
        /***
        *若nearest_event_time等于0x7fffffffffffffff说明此时获取不到当前IOtrace合理的下一状态预计时间，
        但是该IO请求是可以进行处理的，只是下一状态预计时间为最大值，IO会一直被阻塞。
        此时需要更新当前系统时间为IO的到达时间表示IO请求已经开始处理。
        ***/
        ssd->current_time=time_t;           

        //if (ssd->request_queue_length>ssd->parameter->queue_length)    //如果请求队列的长度超过了配置文件中所设置的长度                     
        //{
        //printf("error in get request , the queue length is too long\n");
        //}
    }
    else //不等于0x7fffffffffffffff则nearest_event_time是合理且可用的，获取事件成功也代表着下一状态是可以达到的。此时程序流需要进一步判断该下一状态预计时间是否小于IO的到达时间
    {   
        if(nearest_event_time<time_t) //如果小于的话，说明还没到这条指令到达的时间(不应该执行这条指令)，获取的事件预计时间与实际的IO参数不符
        {
            /*******************************************************************************
             *此时需要执行回滚操作，所谓回滚即当程序或数据处理错误，将程序或数据恢复到上一次正确状态的行为
             *回滚，即如果没有把time_t赋给ssd->current_time，则trace文件已读的一条记录回滚
             *filepoint记录了执行fgets之前的文件指针位置，回滚到文件头+filepoint处
             *int fseek(FILE *stream, long offset, int fromwhere);函数设置文件指针stream的位置。
             *如果执行成功，stream将指向以fromwhere（偏移起始位置：文件头0，当前位置1，文件尾2）为基准，
             *偏移offset（指针偏移量）个字节的位置。如果执行失败(比如offset超过文件自身大小)，则不改变stream指向的位置。
             *文本文件只能采用文件头0的定位方式，本程序中打开文件方式是"r":以只读方式打开文本文件	
             **********************************************************************************/
            fseek(ssd->tracefile,filepoint,0); 
            if(ssd->current_time<=nearest_event_time) 
                ssd->current_time=nearest_event_time; //更新系统时间为下一状态预计时间
            return -1;
        }
        else //需要再进一步确认IO能否正常插入请求队列
        {
            if (ssd->request_queue_length>=ssd->parameter->queue_length) //如果当前ssd中的IO请求队列已经满了，则此时IO是无法正常插入到IO请求队列的
            {
                fseek(ssd->tracefile,filepoint,0); //回滚
                ssd->current_time=nearest_event_time;
                return -1;
            } 
            else //如果IO请求队列并未满,则证明此时当前的IO请求是可以正常插入请求队列中，程序会更新系统时间为IO到达时间。
            {
                ssd->current_time=time_t;
            }
        }
    }

    if(time_t < 0) //若到达时间小于0，说明IO请求非法，此时程序会打印出错信息并且死机；
    {
        printf("error!\n");
        while(1){}
    }

    if(feof(ssd->tracefile)) //读取完所有请求
    {
        request1=NULL;
        return 0;
    }

    request1 = (struct request*)malloc(sizeof(struct request)); //初始化请求
    alloc_assert(request1,"request");
    memset(request1,0, sizeof(struct request));

    //填充请求
    request1->time = time_t;
    request1->lsn = lsn;
    request1->size = size;
    request1->operation = ope;	
    request1->begin_time = time_t;
    request1->response_time = 0;	
    request1->energy_consumption = 0;	
    request1->next_node = NULL;
    request1->distri_flag = 0;              // indicate whether this request has been distributed already
    request1->subs = NULL;
    request1->need_distr_flag = NULL;       //初始化时IO并不需要立刻分布处理
    request1->complete_lsn_count=0;         //record the count of lsn served by buffer
    filepoint = ftell(ssd->tracefile);		// set the file point 更新文件指针指向下一个IOtrace的位置(为什么是ftell？存储这个指针的位置有什么意义？)

    if(ssd->request_queue == NULL)          //The queue is empty
    {
        ssd->request_queue = request1; //通过链表方式管理
        ssd->request_tail = request1;
        ssd->request_queue_length++;
    }
    else
    {			
        (ssd->request_tail)->next_node = request1;	
        ssd->request_tail = request1;			
        ssd->request_queue_length++;
    }

    //将指令添加到scheduler中。这里不阻止请求发往ssd的request_queue，待通过buffer后再将各个阶段添加到scheduler中********gary add
    struct task* task = (struct task*)malloc(sizeof(struct task)); 
    task->task_ope = ope;
    task->total_stage = 0;
    task->total_finished_stage = 0;
    //task->first_stage = NULL;
    task->next_task = NULL;
    task->request = request1;
    task->stage_queue_head = NULL;
    task->stage_queue_tail = NULL;
    task->task_id = ssd->scheduler->total_task_count++; //task的id是请求出现的次序
    task->ready_stage_head = NULL; //可以开始执行的请求，只需要从这个链表中分发请求即可。
    task->running_stage_head = NULL; //正在执行的请求，只需要检查这个链表中的请求是否完成即可。
    task->finish_time = 0; //标记最晚任务完成时间
    ssd->scheduler->task_count++;
    append_task(ssd->scheduler,task);
    request1->task = task; //将task插入到request中
    //add end********************************************

    if (request1->operation >= READ && request1->operation < LAST_NDP)             //计算平均请求大小 1为读 0为写
    {
        ssd->ave_read_size=(ssd->ave_read_size*ssd->read_request_count+request1->size)/(ssd->read_request_count+1);
    } 
    else
    {
        ssd->ave_write_size=(ssd->ave_write_size*ssd->write_request_count+request1->size)/(ssd->write_request_count+1);
    }


    filepoint = ftell(ssd->tracefile);	//为什么又赋值了一遍？
    fgets(buffer, 200, ssd->tracefile);    //寻找下一条请求的到达时间
    sscanf(buffer,"%lld %d %d %d %d",&time_t,&device,&lsn,&size,&ope);
    ssd->next_request_time=time_t; //既然已经提前保存了指令的时间为什么下次又要读出来了再判断是否达到了这个指令的时间
    fseek(ssd->tracefile,filepoint,0); //读了之后回滚到之前指针

    return 1;
}

/**********************************************************************************************************************************************
 *首先buffer是个写buffer，就是为写请求服务的，因为读flash的时间tR为20us，写flash的时间tprog为200us，所以为写服务更能节省时间
 *  读操作：如果命中了buffer，从buffer读，不占用channel的I/O总线，没有命中buffer，从flash读，占用channel的I/O总线，但是不进buffer了
 *  写操作：首先request分成sub_request子请求，如果是动态分配，sub_request挂到ssd->sub_request上，因为不知道要先挂到哪个channel的sub_request上
 *          如果是静态分配则sub_request挂到channel的sub_request链上,同时不管动态分配还是静态分配sub_request都要挂到request的sub_request链上
 *		   因为每处理完一个request，都要在traceoutput文件中输出关于这个request的信息。处理完一个sub_request,就将其从channel的sub_request链
 *		   或ssd的sub_request链上摘除，但是在traceoutput文件输出一条后再清空request的sub_request链。
 *		   sub_request命中buffer则在buffer里面写就行了，并且将该sub_page提到buffer链头(LRU)，若没有命中且buffer满，则先将buffer链尾的sub_request
 *		   写入flash(这会产生一个sub_request写请求，挂到这个请求request的sub_request链上，同时视动态分配还是静态分配挂到channel或ssd的
 *		   sub_request链上),在将要写的sub_page写入buffer链头
 ***********************************************************************************************************************************************/
struct ssd_info *buffer_management(struct ssd_info *ssd)
{   
    unsigned int j,lsn,lpn,last_lpn,first_lpn,index,complete_flag=0, state,full_page;
    unsigned int flag=0,need_distb_flag,lsn_flag,flag1=1,active_region_flag=0;           
    struct request *new_request;
    struct buffer_group *buffer_node,key; //key用于查找缓存是否命中
    unsigned int mask=0,offset1=0,offset2=0;

#ifdef DEBUG
    printf("enter buffer_management,  current time:%lld\n",ssd->current_time);
#endif
    ssd->dram->current_time=ssd->current_time; //设置缓存dram的当前时间为系统的当前时间
    full_page=~(0xffffffff<<ssd->parameter->subpage_page); //初始化子页状态屏蔽码full_page(主要用于后续进行)，用于标记每个子页的状态。例如每个页有四个子页时该变量为b'1111

    new_request=ssd->request_tail; //将new_request指针指向ssd的IO请求队列队尾(为什么要从队尾开始处理？因为进入buffer_management说明get_request函数成功了，获取了一个新请求并插在队尾的；如果没有执行成功则队尾的不是新请求)
    lsn=new_request->lsn; //记录下IO队列队尾结点的lsn信息，因为IO处理是从队列尾部开始的(lsn是逻辑扇区号，就是主机看到的地址)
    lpn=new_request->lsn/ssd->parameter->subpage_page; //根据lsn计算相应的lpn信息、队尾IO请求项操作区间的最大lpn信息(lsn是逻辑页号，是盘内的页面管理单位)
    last_lpn=(new_request->lsn+new_request->size-1)/ssd->parameter->subpage_page; //该IO请求项操作的最大目标页号 = (IO逻辑扇区起始号 + IO操作长度 - 1)/子页数量)
    first_lpn = new_request->lsn/ssd->parameter->subpage_page; //首个lpn信息(first_lpn即该IO请求项操作的起始目标页号 = IO逻辑扇区起始号/子页数量)

    //***********创建初始任务，每个任务(包括NDP)都是由I/O任务开始的，因此可以在这里就先创建一部分子任务***********************gary add
    //为每个lpn创建stage
    if(new_request->operation != WRITE){
        for(int i=first_lpn;i<=last_lpn;i++){
            struct stage* tmp_stage = init_stage();
            //标记基本信息
            tmp_stage->id = new_request->task->total_stage++;
            tmp_stage->ope = new_request->operation==WRITE?WRITE:READ; //因为ndp请求只会读，所以生成的子请求中，如果是写请求就是写(0就是0)，如果是读请求或者ndp请求就是读(大于等于1就是1)，所以取最小值即可
            tmp_stage->lpn = i;
            tmp_stage->predict_time = ssd->parameter->time_characteristics.tR;
            tmp_stage->status = FINISH; //默认是完成的，在create_sub_request中设置为未完成状态。因为已经在buffer命中的stage不会进create_sub_request无法标记为完成状态
            tmp_stage->task = new_request->task;
            tmp_stage->task->total_finished_stage++; //因为默认是完成的，所以要+1.后面create_sub_request的时候再减一

            //将任务链接到子任务中
            link_stage_to_task(tmp_stage->task, tmp_stage);

            //不能在这里将这个阶段添加到可执行stage中，因为不是所有请求都需要执行
        }

        //添加NDP请求
        if(new_request->operation == RECSSD){
            //在每个IO任务后面添加一个计算操作
            struct stage* iter = new_request->task->stage_queue_head; 
            while(iter!=NULL && iter->ope==1){
                struct stage* cal_stage = init_stage(); //新建一个计算任务
                
                cal_stage->id = new_request->task->total_stage++; //total_finished_stage就不用+1了
                cal_stage->ope = RECSSD;
                cal_stage->task = new_request->task;
                cal_stage->predict_time = ssd->parameter->recssd_time;

                //将io任务设为父任务
                add_stage_dependency(cal_stage, iter, PARENT);
                add_stage_dependency(iter, cal_stage, CHILD);
                
                link_stage_to_task(cal_stage->task, cal_stage);

                iter = iter->next_stage_of_task;
            }
            //printf("init a RECSSD task\n");
        }
        else if(new_request->operation == TEXT){
            struct stage* iter = new_request->task->stage_queue_head; 
            while(iter!=NULL && iter->ope==1){
                struct stage* cal_stage = init_stage(); //新建一个计算任务
                
                cal_stage->id = new_request->task->total_stage++; //total_finished_stage就不用+1了
                cal_stage->ope = TEXT;
                cal_stage->task = new_request->task;
                cal_stage->predict_time = ssd->parameter->text_time;

                //将io任务设为父任务
                add_stage_dependency(cal_stage, iter, PARENT);
                add_stage_dependency(iter, cal_stage, CHILD);
                
                link_stage_to_task(cal_stage->task, cal_stage);

                iter = iter->next_stage_of_task;
            }
        }
        else if(new_request->operation == IMAGE){
            //所有数据聚合起来后计算
            struct stage* cal_stage = init_stage(); //新建一个计算任务
            cal_stage->id = new_request->task->total_stage++; //total_finished_stage就不用+1了
            cal_stage->ope = IMAGE;
            cal_stage->task = new_request->task;
            cal_stage->predict_time = ssd->parameter->image_time;
            link_stage_to_task(cal_stage->task, cal_stage);

            struct stage* iter = new_request->task->stage_queue_head; 
            while(iter!=NULL && iter->ope==1){
                //将io任务设为父任务
                add_stage_dependency(cal_stage, iter, PARENT);
                add_stage_dependency(iter, cal_stage, CHILD);
                
                iter = iter->next_stage_of_task;
            }
        }
        else if(new_request->operation >= LAST_NDP){
            printf("[buffer_management]Error! unknown operation %d\n",new_request->operation);
            getchar();
        }

        //打印task结构体验证
        //print_task(new_request->task, "[buffer_management]");
    }

    //************************************************************gary add end

    /*
    对IO请求项中的子页状态位数组need_distr_flag进行一个初始化设置
    这里的子页状态位数组是一个int*类型的结构，使用malloc分配后实际上是一个int数组，其中每一个数组元素都存放着对应的子页状态标志信息，
    这个数组开始分配的长度是由lsn和size决定的，计算原理是：数组长度 = ((总页数×子页数=总子页数即总扇区数)/32+1) <==>相当于子页状态位数量。
    之所以要除以32是因为在一个32位的整型数据中可以用每一个bit来代表着一个子页的对应状态，则一个int类型的数据就可以代表着32个子页的状态，
    用32/subpage_page就可以得到一个32位int可以存放多少个页的全部子页状态，
    需要注意的就是这个子页状态数组的每一个数组元素都代表了请求所涉及到的（32/subpage_page）个页的所有子页状态的情况。
    每一个IO请求项都会有一个这样的子页状态位标志，用来标识子页是否完成操作，若未完成则需要调用creat_sub_request()函数创建相应的子请求。初始化数组时全部置零。
    */
    new_request->need_distr_flag=(unsigned int*)malloc(sizeof(unsigned int)*((last_lpn-first_lpn+1)*ssd->parameter->subpage_page/32+1));
    alloc_assert(new_request->need_distr_flag,"new_request->need_distr_flag");
    memset(new_request->need_distr_flag, 0, sizeof(unsigned int)*((last_lpn-first_lpn+1)*ssd->parameter->subpage_page/32+1));

    if(new_request->operation >= READ && new_request->operation < LAST_NDP) 
    {		
        //当前lpn小于或等于最大目标页号last_lpn时，也就是说明该IO读请求操作尚未完成，则进入一个while循环内部
        while(lpn<=last_lpn)      		
        {
            /************************************************************************************************
             *!!need_disb_flag不是上述IO请求项中的need_distr_flag子页状态位数组
             *need_distb_flag表示是否需要执行distribution函数，1表示需要执行，buffer中没有，0表示不需要执行
             *即1表示需要分发，0表示不需要分发，对应点初始全部赋为1
             *************************************************************************************************/
            need_distb_flag=full_page;   //设置need_disb_flag这个标志变量为子页状态屏蔽码full_page，表示此时该lpn下所有的子页都需要进行处理
            key.group=lpn; //key.group记录当前的lpn。key是一个buffer_group类型的节点，其中每一个buffer节点中都有一个uint类型的group，记录着一个当前缓存数据的起始lpn号
            buffer_node= (struct buffer_group*)avlTreeFind(ssd->dram->buffer, (TREE_NODE *)&key);		//判断该lpn对应的buffer节点是否存在于buffer中

            //读请求缓存命中，说明buffer_node非空，可以直接在buffer中进行读数据；且若当前lsn未超过最后的lsn和当前lpn内的lsn——也就是说当前针对lpn的操作尚未完成时，程序流会进入内部while循环
            //命中且lsn小于buffer的大小，以及lsn没有超过请求大小
            while((buffer_node!=NULL)&&(lsn<(lpn+1)*ssd->parameter->subpage_page)&&(lsn<=(new_request->lsn+new_request->size-1)))             			
            {             	
                lsn_flag=full_page; //需要全部进行读处理
                mask=1 << (lsn%ssd->parameter->subpage_page); //mask记录下当前lsn相对当前lpn起始位置的偏移位置，并标记为1，代表要对lsn位置进行一个子页的读操作
                if(mask>0x80000000)
                {
                    printf("the subpage number is larger than 32!add some cases");
                    getchar(); 		   
                }
                //若mask合理，则置位flag标志为1表示子页读取成功，并更新lsn_flag记录，将mask中对应lsn的子页标志在lsn_flag中清零，代表该子页已经读取完成
                else if((buffer_node->stored & mask)==mask)
                {
                    flag=1; //表示子页读取成功
                    lsn_flag=lsn_flag&(~mask); //为什么只看一个子页呢？因为一次while循环只处理一个lsn
                }

                if(flag==1)	//当存储在缓存中（flag==1），如果该buffer节点不在buffer的队首，需要将这个节点提到队首，并增加读命中次数和当前请求完成lsn次数。否则增加读miss次数			
                {	//如果该buffer节点不在buffer的队首，需要将这个节点提到队首，实现了LRU算法，这个是一个双向队列。		       		
                    if(ssd->dram->buffer->buffer_head!=buffer_node)     
                    {		
                        if(ssd->dram->buffer->buffer_tail==buffer_node)								
                        {			
                            buffer_node->LRU_link_pre->LRU_link_next=NULL;					
                            ssd->dram->buffer->buffer_tail=buffer_node->LRU_link_pre;							
                        }				
                        else								
                        {				
                            buffer_node->LRU_link_pre->LRU_link_next=buffer_node->LRU_link_next;				
                            buffer_node->LRU_link_next->LRU_link_pre=buffer_node->LRU_link_pre;								
                        }								
                        buffer_node->LRU_link_next=ssd->dram->buffer->buffer_head;
                        ssd->dram->buffer->buffer_head->LRU_link_pre=buffer_node;
                        buffer_node->LRU_link_pre=NULL;			
                        ssd->dram->buffer->buffer_head=buffer_node;													
                    }						
                    ssd->dram->buffer->read_hit++;					
                    new_request->complete_lsn_count++;											
                }		
                else if(flag==0)
                {
                    ssd->dram->buffer->read_miss_hit++;
                }

                need_distb_flag=need_distb_flag&lsn_flag;

                if(need_distb_flag)

                flag=0;		
                lsn++;						
            }	

            index=(lpn-first_lpn)/(32/ssd->parameter->subpage_page); 			
            new_request->need_distr_flag[index]=new_request->need_distr_flag[index]|(need_distb_flag<<(((lpn-first_lpn)%(32/ssd->parameter->subpage_page))*ssd->parameter->subpage_page));	
            lpn++;

        }
    }  
    else if(new_request->operation == WRITE)
    {
        while(lpn<=last_lpn)           	
        {	
            need_distb_flag=full_page;
            mask=~(0xffffffff<<(ssd->parameter->subpage_page));
            state=mask;

            if(lpn==first_lpn)
            {
                offset1=ssd->parameter->subpage_page-((lpn+1)*ssd->parameter->subpage_page-new_request->lsn);
                state=state&(0xffffffff<<offset1); //表示需要该lpn操作的lsn
            }
            if(lpn==last_lpn)
            {
                offset2=ssd->parameter->subpage_page-((lpn+1)*ssd->parameter->subpage_page-(new_request->lsn+new_request->size));
                state=state&(~(0xffffffff<<offset2));
            }

            ssd=insert2buffer(ssd, lpn, state,NULL,new_request); //每个lpn都要insert一次，如果可以命中
            lpn++;
        }
    }
    complete_flag = 1; //检查请求need_distb_flag，若存在1则标记未完成，否则标记完成
    for(j=0;j<=(last_lpn-first_lpn+1)*ssd->parameter->subpage_page/32;j++)
    {
        if(new_request->need_distr_flag[j] != 0)
        {
            complete_flag = 0;
        }
    }

    /*************************************************************
     *如果请求已经被全部由buffer服务，该请求可以被直接响应，输出结果
     *这里假设dram的服务时间为1000ns
     *只会在有新请求时被调用一次(未验证)
     **************************************************************/
    if((complete_flag == 1)&&(new_request->subs==NULL))     //          
    {
        new_request->begin_time=ssd->current_time;
        new_request->response_time=ssd->current_time+1000;            
    }

    //gary add**********************************
    //print_task(new_request->task,"[buffer_management]");
    //gary add end******************************

    return ssd;
}

/*****************************
 *lpn向ppn的转换
 ******************************/
unsigned int lpn2ppn(struct ssd_info *ssd,unsigned int lsn)
{
    int lpn, ppn;	
    struct entry *p_map = ssd->dram->map->map_entry;
#ifdef DEBUG
    printf("enter lpn2ppn,  current time:%lld\n",ssd->current_time);
#endif
    lpn = lsn/ssd->parameter->subpage_page;			//lpn
    ppn = (p_map[lpn]).pn;
    return ppn;
}

/**********************************************************************************
 *读请求分配子请求函数，这里只处理读请求，写请求已经在buffer_management()函数中处理了
 *根据请求队列和buffer命中的检查，将每个请求分解成子请求，将子请求队列挂在channel上，
 *不同的channel有自己的子请求队列
 **********************************************************************************/

struct ssd_info *distribute(struct ssd_info *ssd) 
{
    unsigned int start, end, first_lsn,last_lsn,lpn,flag=0,flag_attached=0,full_page;
    unsigned int j, k, sub_size;
    int i=0;
    struct request *req;
    //struct sub_request *sub;
    int* complt;

#ifdef DEBUG
    printf("enter distribute,  current time:%lld\n",ssd->current_time);
#endif
    full_page=~(0xffffffff<<ssd->parameter->subpage_page);

    req = ssd->request_tail;
    if(req->response_time != 0){
        return ssd;
    }
    if (req->operation==WRITE)
    {
        return ssd;
    }

    if(req != NULL)
    {
        if(req->distri_flag == 0) //等于0代表没有处理完（好像没有卵用。。。根本没有用到这个变量）
        {
            //如果还有一些读请求需要处理
            if(req->complete_lsn_count != ssd->request_tail->size)
            {		
                first_lsn = req->lsn;				
                last_lsn = first_lsn + req->size;
                complt = req->need_distr_flag;
                start = first_lsn - first_lsn % ssd->parameter->subpage_page;
                end = (last_lsn/ssd->parameter->subpage_page + 1) * ssd->parameter->subpage_page;
                i = (end - start)/32;	

                while(i >= 0)
                {	
                    /*************************************************************************************
                     *一个32位的整型数据的每一位代表一个子页，32/ssd->parameter->subpage_page就表示有多少页，
                     *这里的每一页的状态都存放在了 req->need_distr_flag中，也就是complt中，通过比较complt的
                     *每一项与full_page，就可以知道，这一页是否处理完成。如果没处理完成则通过creat_sub_request
                     函数创建子请求。
                     *************************************************************************************/
                    for(j=0; j<32/ssd->parameter->subpage_page; j++)
                    {	
                        k = (complt[((end-start)/32-i)] >>(ssd->parameter->subpage_page*j)) & full_page;	
                        if (k !=0)
                        {
                            lpn = start/ssd->parameter->subpage_page+ ((end-start)/32-i)*32/ssd->parameter->subpage_page + j;
                            sub_size=transfer_size(ssd,k,lpn,req);    
                            if (sub_size==0) 
                            {
                                continue;
                            }
                            else
                            {
                                creat_sub_request(ssd,lpn,sub_size,0,req,req->operation);
                            }	
                        }
                    }
                    i = i-1;
                }

            }
            else
            {
                req->begin_time=ssd->current_time;
                req->response_time=ssd->current_time+1000;   
            }

        }
    }
    return ssd;
}


/**********************************************************************
 *trace_output()函数是在每一条请求的所有子请求经过process()函数处理完后，
 *打印输出相关的运行结果到outputfile文件中，这里的结果主要是运行的时间
 **********************************************************************/
void trace_output(struct ssd_info* ssd){
    int flag = 1;	
    int64_t start_time, end_time;
    struct request *req, *pre_node;
    struct sub_request *sub, *tmp;

#ifdef DEBUG
    printf("enter trace_output,  current time:%lld\n",ssd->current_time);
#endif

    pre_node=NULL;
    req = ssd->request_queue;
    start_time = 0;
    end_time = 0;

    if(req == NULL) 
        return;

    while(req != NULL)	
    {
        sub = req->subs;
        flag = 1;
        start_time = 0;
        end_time = 0;

        //gary modify********因为原本的终止条件只能判断挂在req请求队列里面的请求是否都完成了，ndp请求并不在那个队列中，所以当没有全部请求都完成时不能结束该任务
        if(req->task->total_stage - req->task->total_finished_stage > 0){ 
            //printf("task %d unfinished,total:%d,finished:%d\n",req->task->task_id, req->task->total_stage, req->task->total_finished_stage);
            pre_node = req;
            req = req->next_node;
            continue;
        }
        else if(req->task->total_stage - req->task->total_finished_stage < 0){ 
            printf("[trace_output]impossible!\n");
            getchar();
        }
        else{
            //printf("task %d finished\n",req->task->task_id);
        }
        //modify end***********************************

        if(req->response_time != 0) //如果这个指令完成了。只会服务全部命中了的请求
        {
            if(req->response_time < req->task->finish_time)
                req->response_time = req->task->finish_time;

            if(req->subs != NULL){
                printf("impossible!\n");
                getchar();
            }
            fprintf(ssd->outputfile,"%8d %16lld %10d %6d %2d %16lld %16lld %10lld\n",req->task->task_id, req->time,req->lsn, req->size, req->operation, req->begin_time, req->response_time, req->response_time-req->time);
            fflush(ssd->outputfile);

            if(req->response_time-req->begin_time==0)
            {
                printf("the response time is 0?? \n");
                getchar();
            }

            //**********************gary modify
            //统计所有请求的完成时间
            ssd->request_count++;
            ssd->request_avg_time += req->response_time-req->time;
            //*********************************

            if (req->operation == READ)
            {
                ssd->read_request_count++;
                ssd->read_avg=ssd->read_avg+(req->response_time-req->time);
            } 
            else if(req->operation == WRITE)
            {
                ssd->write_request_count++;
                ssd->write_avg=ssd->write_avg+(req->response_time-req->time);
            }
            else if(req->operation>READ && req->operation<LAST_NDP){
                ssd->ndp_count++;
                ssd->ndp_avg_time += req->response_time-req->time;

                if(req->operation == RECSSD){
                    ssd->recssd_count++;
                    //ssd->recssd_avg_time += req->response_time-req->time;
                }
                else if(req->operation == TEXT){
                    ssd->text_count++;
                    //ssd->text_avg_time += req->response_time-req->time;
                }
                else if(req->operation == IMAGE){
                    ssd->image_count++;
                    //ssd->image_avg_time += req->response_time-req->time;
                }
            }

            //将这个req从ssd->request_queue中删除
            if(pre_node == NULL) 
            {
                if(req->next_node == NULL) //说明既没有前一个请求又没有后一个请求，那么ssd->request_queue清空
                {
                    free(req->need_distr_flag);

                    //从scheduler中删除任务gary******************
                    delete_task(req->task); 
                    ssd->scheduler->task_head=NULL;
                    ssd->scheduler->task_tail=NULL;
                    ssd->scheduler->task_count--;
                    //***********************************add end

                    req->need_distr_flag=NULL;
                    free(req);
                    req = NULL;
                    ssd->request_queue = NULL;
                    ssd->request_tail = NULL;
                    ssd->request_queue_length--;
                }
                else //如果没有前一个请求但是还有下一个请求，那么记录当前请求到pre_node中，然后req移动到下一个请求中后把当前请求删了
                {
                    ssd->request_queue = req->next_node;
                    pre_node = req;
                    req = req->next_node;
                    free(pre_node->need_distr_flag);

                    //从scheduler中删除任务gary******************
                    delete_task(pre_node->task); 
                    ssd->scheduler->task_head=req->task;
                    ssd->scheduler->task_count--;
                    //***********************************add end
                    
                    pre_node->need_distr_flag=NULL;
                    free((void *)pre_node);
                    pre_node = NULL;
                    ssd->request_queue_length--;
                }
            }
            else
            {
                if(req->next_node == NULL) //有头没尾
                {
                    pre_node->next_node = NULL;
                    free(req->need_distr_flag);
                    
                    //从scheduler中删除任务gary******************
                    delete_task(req->task); 
                    ssd->scheduler->task_tail=pre_node->task;
                    ssd->scheduler->task_tail->next_task=NULL;
                    ssd->scheduler->task_count--;
                    //***********************************add end

                    req->need_distr_flag=NULL;
                    free(req);
                    req = NULL;
                    ssd->request_tail = pre_node;
                    ssd->request_queue_length--;
                }
                else //有头有尾
                {
                    pre_node->next_node = req->next_node;
                    free(req->need_distr_flag);
                    
                    //从scheduler中删除任务gary******************
                    pre_node->task->next_task = req->task->next_task;
                    delete_task(req->task); 
                    ssd->scheduler->task_count--;
                    //***********************************add end

                    req->need_distr_flag=NULL;
                    free((void *)req);
                    req = pre_node->next_node;
                    ssd->request_queue_length--;
                }
            }
        }
        else //没有设置指令返回时间，那么遍历子请求看看有没有都完成
        {
            flag=1;
            while(sub != NULL)
            {
                //设置最早完成时间和最晚完成时间
                if(start_time == 0)
                    start_time = sub->begin_time;
                if(start_time > sub->begin_time)
                    start_time = sub->begin_time;
                if(end_time < sub->complete_time)
                    end_time = sub->complete_time;
                if((sub->current_state == SR_COMPLETE)||((sub->next_state==SR_COMPLETE)&&(sub->next_state_predict_time<=ssd->current_time)))	// if any sub-request is not completed, the request is not completed
                {
                    sub = sub->next_subs;
                }
                else
                {
                    flag=0; //如果有一个没完成的则退出
                    break;
                }

            }

            if (flag == 1) //如果所有的sub都完成了
            {
                //gary add*******************************
                //printf("task %d not set complete time\n",req->task->task_id);	
                if(end_time < req->task->finish_time){
                    end_time = req->task->finish_time;
                }
                //add end********************************
                //fprintf(ssd->outputfile,"%10I64u %10u %6u %2u %16I64u %16I64u %10I64u\n",req->time,req->lsn, req->size, req->operation, start_time, end_time, end_time-req->time);
                fprintf(ssd->outputfile,"%8d %16lld %10d %6d %2d %16lld %16lld %10lld\n",req->task->task_id,req->time,req->lsn, req->size, req->operation, start_time, end_time, end_time-req->time);
                fflush(ssd->outputfile);

                if(end_time-start_time==0)
                {
                    printf("the response time is 0?? \n");
                    getchar();
                }

                //**********************gary modify
                //统计所有请求的完成时间
                ssd->request_count++;
                ssd->request_avg_time += end_time-req->time;
                //*********************************

                if (req->operation == READ)
                {
                    ssd->read_request_count++;
                    ssd->read_avg=ssd->read_avg+(end_time-req->time);
                } 
                else if(req->operation == WRITE)
                {
                    ssd->write_request_count++;
                    ssd->write_avg=ssd->write_avg+(end_time-req->time);
                }
                else if(req->operation>READ && req->operation<LAST_NDP){
                    ssd->ndp_count++;
                    ssd->ndp_avg_time += end_time-req->time;

                    if(req->operation == RECSSD){
                        ssd->recssd_count++;
                        ssd->recssd_avg_time += end_time-req->time;
                    }
                    else if(req->operation == TEXT){
                        ssd->text_count++;
                        ssd->text_avg_time += end_time-req->time;
                    }
                    else if(req->operation == IMAGE){
                        ssd->image_count++;
                        ssd->image_avg_time += end_time-req->time;
                    }
                }

                while(req->subs!=NULL) //释放所有的子请求。之前的不用这个步骤，因为前面的只会服务全部在buffer命中了的写请求，不会有子请求
                {
                    tmp = req->subs;
                    req->subs = tmp->next_subs;
                    if (tmp->update!=NULL)
                    {
                        free(tmp->update->location);
                        tmp->update->location=NULL;
                        free(tmp->update);
                        tmp->update=NULL;
                    }
                    free(tmp->location);
                    tmp->location=NULL;
                    free(tmp);
                    tmp=NULL;

                }

                if(pre_node == NULL)
                {
                    if(req->next_node == NULL)
                    {
                        free(req->need_distr_flag);
                        //从scheduler中删除任务gary******************
                        delete_task(req->task); 
                        ssd->scheduler->task_head=NULL;
                        ssd->scheduler->task_tail=NULL;
                        ssd->scheduler->task_count--;
                        //***********************************add end
                        req->need_distr_flag=NULL;
                        free(req);
                        req = NULL;
                        ssd->request_queue = NULL;
                        ssd->request_tail = NULL;
                        ssd->request_queue_length--;
                    }
                    else
                    {
                        ssd->request_queue = req->next_node;
                        pre_node = req;
                        req = req->next_node;
                        free(pre_node->need_distr_flag);
                        //从scheduler中删除任务gary******************
                        delete_task(pre_node->task); 
                        ssd->scheduler->task_head=req->task;
                        ssd->scheduler->task_count--;
                        //***********************************add end
                        pre_node->need_distr_flag=NULL;
                        free(pre_node);
                        pre_node = NULL;
                        ssd->request_queue_length--;
                    }
                }
                else
                {
                    if(req->next_node == NULL)
                    {
                        pre_node->next_node = NULL;
                        free(req->need_distr_flag);
                        //从scheduler中删除任务gary******************
                        delete_task(req->task); 
                        ssd->scheduler->task_tail=pre_node->task;
                        ssd->scheduler->task_tail->next_task=NULL; //pre_node的next指向的是已经被删掉的req
                        ssd->scheduler->task_count--;
                        //***********************************add end

                        req->need_distr_flag=NULL;
                        free(req);
                        req = NULL;
                        ssd->request_tail = pre_node;	
                        ssd->request_queue_length--;
                    }
                    else
                    {
                        pre_node->next_node = req->next_node;
                        free(req->need_distr_flag);
                         //从scheduler中删除任务gary******************
                        pre_node->task->next_task = req->task->next_task;
                        delete_task(req->task); 
                        ssd->scheduler->task_count--;
                        //***********************************add end
                        req->need_distr_flag=NULL;
                        free(req);
                        req = pre_node->next_node;
                        ssd->request_queue_length--;
                    }

                }
            }
            else //如果不是所有sub都完成了
            {	
                pre_node = req;
                req = req->next_node;
            }
        }		
    }
}


/*******************************************************************************
 *statistic_output()函数主要是输出处理完一条请求后的相关处理信息。
 *1，计算出每个plane的擦除次数即plane_erase和总的擦除次数即erase
 *2，打印min_lsn，max_lsn，read_count，program_count等统计信息到文件outputfile中。
 *3，打印相同的信息到文件statisticfile中
 *******************************************************************************/
void statistic_output(struct ssd_info *ssd)
{
    unsigned int lpn_count=0,i,j,k,m,erase=0,plane_erase=0;
    double gc_energy=0.0;
#ifdef DEBUG
    printf("enter statistic_output,  current time:%lld\n",ssd->current_time);
#endif

    for(i=0;i<ssd->parameter->channel_number;i++)
    {
        for(j=0;j<ssd->parameter->die_chip;j++)
        {
            for(k=0;k<ssd->parameter->plane_die;k++)
            {
                plane_erase=0;
                for(m=0;m<ssd->parameter->block_plane;m++)
                {
                    if(ssd->channel_head[i].chip_head[0].die_head[j].plane_head[k].blk_head[m].erase_count>0)
                    {
                        erase=erase+ssd->channel_head[i].chip_head[0].die_head[j].plane_head[k].blk_head[m].erase_count;
                        plane_erase+=ssd->channel_head[i].chip_head[0].die_head[j].plane_head[k].blk_head[m].erase_count;
                    }
                }
                fprintf(ssd->outputfile,"the %d channel, %d chip, %d die, %d plane has : %13d erase operations\n",i,j,k,m,plane_erase);
                fprintf(ssd->statisticfile,"the %d channel, %d chip, %d die, %d plane has : %13d erase operations\n",i,j,k,m,plane_erase);
            }
        }
    }

    if(ssd->read_request_count == 0)
        ssd->read_request_count = 1;
    if(ssd->write_request_count == 0)
        ssd->write_request_count = 1;

    fprintf(ssd->outputfile,"\n");
    fprintf(ssd->outputfile,"\n");
    fprintf(ssd->outputfile,"---------------------------statistic data---------------------------\n");	 
    fprintf(ssd->outputfile,"min lsn: %13d\n",ssd->min_lsn);	
    fprintf(ssd->outputfile,"max lsn: %13d\n",ssd->max_lsn);
    fprintf(ssd->outputfile,"read count: %13d\n",ssd->read_count);	  
    fprintf(ssd->outputfile,"program count: %13d",ssd->program_count);	
    fprintf(ssd->outputfile,"                        include the flash write count leaded by read requests\n");
    fprintf(ssd->outputfile,"the read operation leaded by un-covered update count: %13d\n",ssd->update_read_count);
    fprintf(ssd->outputfile,"erase count: %13d\n",ssd->erase_count);
    fprintf(ssd->outputfile,"direct erase count: %13d\n",ssd->direct_erase_count);
    fprintf(ssd->outputfile,"copy back count: %13d\n",ssd->copy_back_count);
    fprintf(ssd->outputfile,"multi-plane program count: %13d\n",ssd->m_plane_prog_count);
    fprintf(ssd->outputfile,"multi-plane read count: %13d\n",ssd->m_plane_read_count);
    fprintf(ssd->outputfile,"interleave write count: %13d\n",ssd->interleave_count);
    fprintf(ssd->outputfile,"interleave read count: %13d\n",ssd->interleave_read_count);
    fprintf(ssd->outputfile,"interleave two plane and one program count: %13d\n",ssd->inter_mplane_prog_count);
    fprintf(ssd->outputfile,"interleave two plane count: %13d\n",ssd->inter_mplane_count);
    fprintf(ssd->outputfile,"gc copy back count: %13d\n",ssd->gc_copy_back);
    fprintf(ssd->outputfile,"write flash count: %13d\n",ssd->write_flash_count);
    fprintf(ssd->outputfile,"interleave erase count: %13d\n",ssd->interleave_erase_count);
    fprintf(ssd->outputfile,"multiple plane erase count: %13d\n",ssd->mplane_erase_conut);
    fprintf(ssd->outputfile,"interleave multiple plane erase count: %13d\n",ssd->interleave_mplane_erase_count);
    fprintf(ssd->outputfile,"read request count: %13d\n",ssd->read_request_count);
    fprintf(ssd->outputfile,"write request count: %13d\n",ssd->write_request_count);
    fprintf(ssd->outputfile,"read request average size: %13f\n",ssd->ave_read_size);
    fprintf(ssd->outputfile,"write request average size: %13f\n",ssd->ave_write_size);
    fprintf(ssd->outputfile,"read request average response time: %lld\n",ssd->read_avg/ssd->read_request_count);
    fprintf(ssd->outputfile,"write request average response time: %lld\n",ssd->write_avg/ssd->write_request_count);
    fprintf(ssd->outputfile,"buffer read hits: %13d\n",ssd->dram->buffer->read_hit);
    fprintf(ssd->outputfile,"buffer read miss: %13d\n",ssd->dram->buffer->read_miss_hit);
    fprintf(ssd->outputfile,"buffer write hits: %13d\n",ssd->dram->buffer->write_hit);
    fprintf(ssd->outputfile,"buffer write miss: %13d\n",ssd->dram->buffer->write_miss_hit);
    fprintf(ssd->outputfile,"erase: %13d\n",erase);
    fflush(ssd->outputfile);

    fclose(ssd->outputfile);


    fprintf(ssd->statisticfile,"\n");
    fprintf(ssd->statisticfile,"\n");
    fprintf(ssd->statisticfile,"---------------------------statistic data---------------------------\n");	
    fprintf(ssd->statisticfile,"min lsn: %13d\n",ssd->min_lsn);	
    fprintf(ssd->statisticfile,"max lsn: %13d\n",ssd->max_lsn);
    fprintf(ssd->statisticfile,"read count: %13d\n",ssd->read_count);	  
    fprintf(ssd->statisticfile,"program count: %13d",ssd->program_count);	  
    fprintf(ssd->statisticfile,"                        include the flash write count leaded by read requests\n");
    fprintf(ssd->statisticfile,"the read operation leaded by un-covered update count: %13d\n",ssd->update_read_count);
    fprintf(ssd->statisticfile,"erase count: %13d\n",ssd->erase_count);	  
    fprintf(ssd->statisticfile,"direct erase count: %13d\n",ssd->direct_erase_count);
    fprintf(ssd->statisticfile,"copy back count: %13d\n",ssd->copy_back_count);
    fprintf(ssd->statisticfile,"multi-plane program count: %13d\n",ssd->m_plane_prog_count);
    fprintf(ssd->statisticfile,"multi-plane read count: %13d\n",ssd->m_plane_read_count);
    fprintf(ssd->statisticfile,"interleave count: %13d\n",ssd->interleave_count);
    fprintf(ssd->statisticfile,"interleave read count: %13d\n",ssd->interleave_read_count);
    fprintf(ssd->statisticfile,"interleave two plane and one program count: %13d\n",ssd->inter_mplane_prog_count);
    fprintf(ssd->statisticfile,"interleave two plane count: %13d\n",ssd->inter_mplane_count);
    fprintf(ssd->statisticfile,"gc copy back count: %13d\n",ssd->gc_copy_back);
    fprintf(ssd->statisticfile,"write flash count: %13d\n",ssd->write_flash_count);
    fprintf(ssd->statisticfile,"waste page count: %13d\n",ssd->waste_page_count);
    fprintf(ssd->statisticfile,"interleave erase count: %13d\n",ssd->interleave_erase_count);
    fprintf(ssd->statisticfile,"multiple plane erase count: %13d\n",ssd->mplane_erase_conut);
    fprintf(ssd->statisticfile,"interleave multiple plane erase count: %13d\n",ssd->interleave_mplane_erase_count);
    fprintf(ssd->statisticfile,"read request count: %13d\n",ssd->read_request_count);
    fprintf(ssd->statisticfile,"write request count: %13d\n",ssd->write_request_count);
    fprintf(ssd->statisticfile,"read request average size: %13f\n",ssd->ave_read_size);
    fprintf(ssd->statisticfile,"write request average size: %13f\n",ssd->ave_write_size);
    fprintf(ssd->statisticfile,"read request average response time: %lld\n",ssd->read_avg/ssd->read_request_count);
    fprintf(ssd->statisticfile,"write request average response time: %lld\n",ssd->write_avg/ssd->write_request_count);
    fprintf(ssd->statisticfile,"buffer read hits: %13d\n",ssd->dram->buffer->read_hit);
    fprintf(ssd->statisticfile,"buffer read miss: %13d\n",ssd->dram->buffer->read_miss_hit);
    fprintf(ssd->statisticfile,"buffer write hits: %13d\n",ssd->dram->buffer->write_hit);
    fprintf(ssd->statisticfile,"buffer write miss: %13d\n",ssd->dram->buffer->write_miss_hit);
    fprintf(ssd->statisticfile,"erase: %13d\n",erase);

    if(ssd->ndp_count == 0)
        ssd->ndp_count++; //不能让他除0
    if(ssd->recssd_count == 0)
        ssd->recssd_count++; //不能让他除0
    if(ssd->text_count == 0)
        ssd->text_count++; //不能让他除0
    if(ssd->image_count == 0)
        ssd->image_count++; //不能让他除0

    fprintf(ssd->statisticfile,"request average response time: %lld\n",ssd->request_avg_time/ssd->request_count);
    fprintf(ssd->statisticfile,"NDP average response time: %lld\n",ssd->ndp_avg_time/ssd->ndp_count);
    fprintf(ssd->statisticfile,"RecSSD average response time: %lld\n",ssd->recssd_avg_time/ssd->recssd_count);
    fprintf(ssd->statisticfile,"Text average response time: %lld\n",ssd->text_avg_time/ssd->text_count);
    fprintf(ssd->statisticfile,"Image average response time: %lld\n",ssd->image_avg_time/ssd->image_count);

    fflush(ssd->statisticfile);

    fclose(ssd->statisticfile);
}


/***********************************************************************************
 *根据每一页的状态计算出每一需要处理的子页的数目，也就是一个子请求需要处理的子页的页数
 ************************************************************************************/
unsigned int size(unsigned int stored)
{
    unsigned int i,total=0,mask=0x80000000;

#ifdef DEBUG
    printf("enter size\n");
#endif
    for(i=1;i<=32;i++)
    {
        if(stored & mask) total++;
        stored<<=1;
    }
#ifdef DEBUG
    printf("leave size\n");
#endif
    return total;
}


/*********************************************************
 *transfer_size()函数的作用就是计算出子请求的需要处理的size
 *函数中单独处理了first_lpn，last_lpn这两个特别情况，因为这
 *两种情况下很有可能不是处理一整页而是处理一页的一部分，因
 *为lsn有可能不是一页的第一个子页。
 *********************************************************/
unsigned int transfer_size(struct ssd_info *ssd,int need_distribute,unsigned int lpn,struct request *req)
{
    unsigned int first_lpn,last_lpn,state,trans_size;
    unsigned int mask=0,offset1=0,offset2=0;

    first_lpn=req->lsn/ssd->parameter->subpage_page;
    last_lpn=(req->lsn+req->size-1)/ssd->parameter->subpage_page;

    mask=~(0xffffffff<<(ssd->parameter->subpage_page));
    state=mask;
    if(lpn==first_lpn)
    {
        offset1=ssd->parameter->subpage_page-((lpn+1)*ssd->parameter->subpage_page-req->lsn);
        state=state&(0xffffffff<<offset1);
    }
    if(lpn==last_lpn)
    {
        offset2=ssd->parameter->subpage_page-((lpn+1)*ssd->parameter->subpage_page-(req->lsn+req->size));
        state=state&(~(0xffffffff<<offset2));
    }

    trans_size=size(state&need_distribute);

    return trans_size;
}


/**********************************************************************************************************  
 *int64_t find_nearest_event(struct ssd_info *ssd)       
 *寻找所有子请求的最早到达的下个状态时间,首先看请求的下一个状态时间，如果请求的下个状态时间小于等于当前时间，
 *说明请求被阻塞，需要查看channel或者对应die的下一状态时间。Int64是有符号 64 位整数数据类型，值类型表示值介于
 *-2^63 ( -9,223,372,036,854,775,808)到2^63-1(+9,223,372,036,854,775,807 )之间的整数。存储空间占 8 字节。
 *channel,die是事件向前推进的关键因素，三种情况可以使事件继续向前推进，channel，die分别回到idle状态，die中的
 *读数据准备好了
 ***********************************************************************************************************/
int64_t find_nearest_event(struct ssd_info *ssd)  //寻找 所有独立单元的channel下 和 每个channel下所有独立单元chip 的状态情况，从中确定出当前ssd所有子请求中最早到达的下一状态时间。
{
    unsigned int i,j;
    int64_t time=MAX_INT64;
    int64_t time1=MAX_INT64;
    int64_t time2=MAX_INT64;
    int64_t time3=MAX_INT64; //IP核的时间

    for (i=0;i<ssd->parameter->channel_number;i++)
    {
        if (ssd->channel_head[i].next_state==CHANNEL_IDLE) //为什么只有下一状态是IDLE的时候才赋值？
            if(time1>ssd->channel_head[i].next_state_predict_time)
                if (ssd->channel_head[i].next_state_predict_time>ssd->current_time)    
                    time1=ssd->channel_head[i].next_state_predict_time;
        for (j=0;j<ssd->parameter->chip_channel[i];j++)
        {
            if ((ssd->channel_head[i].chip_head[j].next_state==CHIP_IDLE)||(ssd->channel_head[i].chip_head[j].next_state==CHIP_DATA_TRANSFER))
                if(time2>ssd->channel_head[i].chip_head[j].next_state_predict_time)
                    if (ssd->channel_head[i].chip_head[j].next_state_predict_time>ssd->current_time)    
                        time2=ssd->channel_head[i].chip_head[j].next_state_predict_time;	
        }   
    } 

    //找到各个ip核的最近状态时间************************gary add
    for(i=0;i<ssd->parameter->recssd_count;i++){
        if(ssd->recssd_unit_head[i].current_state == RUNNING) //下一状态不是ready的话说明没有任务正在执行，不用处理
            if(time3 > ssd->recssd_unit_head[i].next_state_predict_time) //没有早于当前的最小时间的话也不用赋值
                if(ssd->recssd_unit_head[i].next_state_predict_time > ssd->current_time) //没有大于当前系统时间，说明当前请求还没处理完，也不用赋值
                    time3 = ssd->recssd_unit_head[i].next_state_predict_time;
    }
    for(i=0;i<ssd->parameter->text_count;i++){
        if(ssd->image_unit_head[i].current_state == RUNNING)
            if(time3 > ssd->image_unit_head[i].next_state_predict_time)
                if(ssd->image_unit_head[i].next_state_predict_time > ssd->current_time)
                    time3 = ssd->image_unit_head[i].next_state_predict_time;
    }
    for(i=0;i<ssd->parameter->image_count;i++){
        if(ssd->text_unit_head[i].current_state == RUNNING)
            if(time3 > ssd->text_unit_head[i].next_state_predict_time)
                if(ssd->text_unit_head[i].next_state_predict_time > ssd->current_time)
                    time3 = ssd->text_unit_head[i].next_state_predict_time;
    }
    //************************gary add end

    /*****************************************************************************************************
     *time为所有 A.下一状态为CHANNEL_IDLE且下一状态预计时间大于ssd当前时间的CHANNEL的下一状态预计时间
     *           B.下一状态为CHIP_IDLE且下一状态预计时间大于ssd当前时间的DIE的下一状态预计时间
     *		     C.下一状态为CHIP_DATA_TRANSFER且下一状态预计时间大于ssd当前时间的DIE的下一状态预计时间
     *CHIP_DATA_TRANSFER读准备好状态，数据已从介质传到了register，下一状态是从register传往buffer中的最小值 
     *注意可能都没有满足要求的time，这时time返回0x7fffffffffffffff 。
     *****************************************************************************************************/
    time=(time1>time2)?time2:time1;
    time=(time>time3)?time3:time;
    return time;
}

/***********************************************
 *free_all_node()函数的作用就是释放所有申请的节点
 ************************************************/
void free_all_node(struct ssd_info *ssd)
{
    unsigned int i,j,k,l,n;
    struct buffer_group *pt=NULL;
    struct direct_erase * erase_node=NULL;
    for (i=0;i<ssd->parameter->channel_number;i++)
    {
        for (j=0;j<ssd->parameter->chip_channel[0];j++)
        {
            for (k=0;k<ssd->parameter->die_chip;k++)
            {
                for (l=0;l<ssd->parameter->plane_die;l++)
                {
                    for (n=0;n<ssd->parameter->block_plane;n++)
                    {
                        free(ssd->channel_head[i].chip_head[j].die_head[k].plane_head[l].blk_head[n].page_head);
                        ssd->channel_head[i].chip_head[j].die_head[k].plane_head[l].blk_head[n].page_head=NULL;
                    }
                    free(ssd->channel_head[i].chip_head[j].die_head[k].plane_head[l].blk_head);
                    ssd->channel_head[i].chip_head[j].die_head[k].plane_head[l].blk_head=NULL;
                    while(ssd->channel_head[i].chip_head[j].die_head[k].plane_head[l].erase_node!=NULL)
                    {
                        erase_node=ssd->channel_head[i].chip_head[j].die_head[k].plane_head[l].erase_node;
                        ssd->channel_head[i].chip_head[j].die_head[k].plane_head[l].erase_node=erase_node->next_node;
                        free(erase_node);
                        erase_node=NULL;
                    }
                }

                free(ssd->channel_head[i].chip_head[j].die_head[k].plane_head);
                ssd->channel_head[i].chip_head[j].die_head[k].plane_head=NULL;
            }
            free(ssd->channel_head[i].chip_head[j].die_head);
            ssd->channel_head[i].chip_head[j].die_head=NULL;
        }
        free(ssd->channel_head[i].chip_head);
        ssd->channel_head[i].chip_head=NULL;
    }
    free(ssd->channel_head);
    ssd->channel_head=NULL;

    avlTreeDestroy( ssd->dram->buffer);
    ssd->dram->buffer=NULL;

    free(ssd->dram->map->map_entry);
    ssd->dram->map->map_entry=NULL;
    free(ssd->dram->map);
    ssd->dram->map=NULL;
    free(ssd->dram);
    ssd->dram=NULL;
    free(ssd->parameter);
    ssd->parameter=NULL;

    free(ssd);
    ssd=NULL;
}


/*****************************************************************************
 *make_aged()函数的作用就死模拟真实的用过一段时间的ssd，
 *那么这个ssd的相应的参数就要改变，所以这个函数实质上就是对ssd中各个参数的赋值。
 ******************************************************************************/
struct ssd_info *make_aged(struct ssd_info *ssd)
{
    unsigned int i,j,k,l,m,n,ppn;
    int threshould,flag=0;

    if (ssd->parameter->aged==1)
    {
        //threshold表示一个plane中有多少页需要提前置为失效
        threshould=(int)(ssd->parameter->block_plane*ssd->parameter->page_block*ssd->parameter->aged_ratio);  
        for (i=0;i<ssd->parameter->channel_number;i++)
            for (j=0;j<ssd->parameter->chip_channel[i];j++)
                for (k=0;k<ssd->parameter->die_chip;k++)
                    for (l=0;l<ssd->parameter->plane_die;l++)
                    {  
                        flag=0;
                        for (m=0;m<ssd->parameter->block_plane;m++)
                        {  
                            if (flag>=threshould)
                            {
                                break;
                            }
                            for (n=0;n<(ssd->parameter->page_block*ssd->parameter->aged_ratio+1);n++)
                            {  
                                ssd->channel_head[i].chip_head[j].die_head[k].plane_head[l].blk_head[m].page_head[n].valid_state=0;        //表示某一页失效，同时标记valid和free状态都为0
                                ssd->channel_head[i].chip_head[j].die_head[k].plane_head[l].blk_head[m].page_head[n].free_state=0;         //表示某一页失效，同时标记valid和free状态都为0
                                ssd->channel_head[i].chip_head[j].die_head[k].plane_head[l].blk_head[m].page_head[n].lpn=0;  //把valid_state free_state lpn都置为0表示页失效，检测的时候三项都检测，单独lpn=0可以是有效页
                                ssd->channel_head[i].chip_head[j].die_head[k].plane_head[l].blk_head[m].free_page_num--;
                                ssd->channel_head[i].chip_head[j].die_head[k].plane_head[l].blk_head[m].invalid_page_num++;
                                ssd->channel_head[i].chip_head[j].die_head[k].plane_head[l].blk_head[m].last_write_page++;
                                ssd->channel_head[i].chip_head[j].die_head[k].plane_head[l].free_page--;
                                flag++;

                                ppn=find_ppn(ssd,i,j,k,l,m,n);

                            }
                        } 
                    }	 
    }  
    else
    {
        return ssd;
    }

    return ssd;
}


/*********************************************************************************************
 *no_buffer_distribute()函数是处理当ssd没有dram的时候，
 *这是读写请求就不必再需要在buffer里面寻找，直接利用creat_sub_request()函数创建子请求，再处理。
 *********************************************************************************************/
struct ssd_info *no_buffer_distribute(struct ssd_info *ssd)
{
    unsigned int lsn,lpn,last_lpn,first_lpn,complete_flag=0, state;
    unsigned int flag=0,flag1=1,active_region_flag=0;           //to indicate the lsn is hitted or not
    struct request *req=NULL;
    struct sub_request *sub=NULL,*sub_r=NULL,*update=NULL;
    struct local *loc=NULL;
    struct channel_info *p_ch=NULL;


    unsigned int mask=0; 
    unsigned int offset1=0, offset2=0;
    unsigned int sub_size=0;
    unsigned int sub_state=0;

    ssd->dram->current_time=ssd->current_time;
    req=ssd->request_tail;       
    lsn=req->lsn;
    lpn=req->lsn/ssd->parameter->subpage_page;
    last_lpn=(req->lsn+req->size-1)/ssd->parameter->subpage_page;
    first_lpn=req->lsn/ssd->parameter->subpage_page;

    if(req->operation==READ)        
    {		
        while(lpn<=last_lpn) 		
        {
            sub_state=(ssd->dram->map->map_entry[lpn].state&0x7fffffff);
            sub_size=size(sub_state);
            sub=creat_sub_request(ssd,lpn,sub_size,sub_state,req,req->operation);
            lpn++;
        }
    }
    else if(req->operation==WRITE)
    {
        while(lpn<=last_lpn)     	
        {	
            mask=~(0xffffffff<<(ssd->parameter->subpage_page));
            state=mask;
            if(lpn==first_lpn)
            {
                offset1=ssd->parameter->subpage_page-((lpn+1)*ssd->parameter->subpage_page-req->lsn);
                state=state&(0xffffffff<<offset1);
            }
            if(lpn==last_lpn)
            {
                offset2=ssd->parameter->subpage_page-((lpn+1)*ssd->parameter->subpage_page-(req->lsn+req->size));
                state=state&(~(0xffffffff<<offset2));
            }
            sub_size=size(state);

            sub=creat_sub_request(ssd,lpn,sub_size,state,req,req->operation);
            lpn++;
        }
    }

    return ssd;
}


